//
//  Problem1329.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/16.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1329. 将矩阵按对角线排序
 矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。

 给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。

 示例 1：
     输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
     输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
 示例 2：
     输入：mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
     输出：[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]
 提示：
     m == mat.length
     n == mat[i].length
     1 <= m, n <= 100
     1 <= mat[i][j] <= 100
 */
@objcMembers class Problem1329: NSObject {
    func solution() {
        print(diagonalSort([[3,3,1,1],[2,2,1,2],[1,1,1,2]]))
        print(diagonalSort([[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]))
    }
    
    /*
     1: 获取每个节点的对角线数据，然后排列
     2: 把排好序的数据，然后放到矩阵中
     
     */
    func diagonalSort(_ mat: [[Int]]) -> [[Int]] {
        var map:[Int: [Int]] = [:]
        
        // 1: 获取矩阵对角线
        for i in 0..<mat.count {
            for j in 0..<mat[i].count {
                map[i-j, default: []].append(mat[i][j])
            }
        }
        // 2: 排序
        for key in map.keys {
            map[key]!.sort()
        }
        // 3: 插入到矩阵中
        var result = mat
        for i in 0..<result.count {
            for j in 0..<result[i].count {
                result[i][j] = map[i-j]!.removeFirst()
            }
        }
        return result
    }
}
